package Algorithm.Dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//https://leetcode-cn.com/problems/largest-divisible-subset/
//368. 最大整除子集
public class Leetcode368 {
    class Solution {
        public List<Integer> largestDivisibleSubset(int[] nums) {
            int[] dp = new int[nums.length];
            int[] g = new int[nums.length];

            Arrays.sort(nums);
            int max = 0;
            int index = 0;
            for(int i=0;i<nums.length;i++){
                dp[i] = 1;
                g[i] = i;

                for(int j=0;j<i;j++){
                    if(nums[i]%nums[j]==0){
                        if(dp[i]<dp[j]+1){
                            dp[i] = dp[j] + 1;
                            g[i] = j;
                        }

                        if(dp[i]>max){
                            max = dp[i];
                            index = i;
                        }
                    }
                }
            }

            List<Integer> result = new ArrayList();

            while(g[index]!=index){
                result.add(nums[index]);
                index = g[index];
            }
            result.add(nums[index]);
            return result;
        }
    }
}
